// 归并排序，ACM练习风格
// 测试链接 : https://www.nowcoder.com/practice/bc25055fb97e4a0bb564cb4b214ffa92
// 提交以下的code，可以直接通过

// 题目没有说数据量，按道理是要说的
// 根据实验，长度500以内够用了
// 如果有一天牛客升级了数据量导致出错
// 把这个值改大即可

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5001;
int arr[MAXN];
int help[MAXN];
int n;

// l....r 一共有n个数
// O(n)
void merge(int l, int m, int r)
{
    int i = l, a = l, b = m + 1;
    while(a <= m && b <= r)
    {
        help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
    }

    // 左侧指针、右侧指针，必有一个越界、另一个不越界
    while(a <= m) help[i++] = arr[a++];
    while(b <= r) help[i++] = arr[b++];
    for(i = l; i <= r; ++i) arr[i] = help[i];
}


// 归并排序递归版
// 假设l...r一共n个数
// T(n) = 2 * T(n/2) + O(n)
// a = 2, b = 2, c = 1
// 根据master公式，时间复杂度O(n * logn)
// 空间复杂度O(n)
void mergeSort1(int l, int r)
{
    if(l >= r) return;

    int m = l + ((r - l) >> 1);
    mergeSort1(l, m);
    mergeSort1(m + 1, r);
    merge(l, m, r);
}

// 归并排序非递归版
// 时间复杂度O(n * logn)
// 空间复杂度O(n)
void mergeSort2()
{
    // 一共发生O(logn)次
    for(int l, m, r, step = 1; step < n; step <<= 1)
    {
        // 内部分组merge，时间复杂度O(n)
        l = 0;
        while(l < n) // 左侧有数字
        {
            m = l + step - 1; // 计算左边部分的右边界
            if(m + 1 >= n) // m + 1 是右侧部分的开头，没有右侧的部分
            {
                break;
            }
            // 有右侧部分，求右侧部分的右边界
            r = min(l + (step << 1) - 1, n - 1); // 看看右侧够不够 step 个数
            merge(l, m, r);
            // 去合并下一组
            l = r + 1;
        }
    }
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
    {
        scanf("%d", &arr[i]);
    }

    // mergeSort1为递归方法
    // mergeSort2为非递归方法
    // 用哪个都可以
    // mergeSort1(0, n - 1);
    mergeSort2();
    for(int i = 0; i < n; ++i) printf("%d ", arr[i]);
    printf("\n");

    return 0;
}